#include <vector>
#include <cstdio>
#include "node.h"

// Function: reverse_in_place1
//
// Reverse a linked list.
// Use a vector to store all nodes' addresses, then use backwards traversal
// to reverse the list by redirecting nodes' next pointers.
//
// Input: Node *& head
// Return: pointer to new head node
Node * reverse_in_place1(Node *& head)
{
    if (NULL == head)
    {
        return NULL;
    }

    // use a vector to store all nodes' addresses
    std::vector<Node *> node_addrs;
    while(head != NULL)
    {
        node_addrs.push_back(head);
        head = head->next();
    }

    // reverse traversal the vector
    std::vector<Node *>::reverse_iterator it1 = node_addrs.rbegin();
    std::vector<Node *>::reverse_iterator it2;
    while(true)
    {
        it2 = it1++; // get previous node in it1 and current node in it2
        if (node_addrs.rend() == it1)
        {
            (*it2)->set_next(NULL);
            break;
        }
        else
        {
            (*it2)->set_next(*it1);
        }
    }

    // get new list head
    head = node_addrs.back();
    return head;
}

// Function: reverse_in_place2
//
// Reverse a linked list.
// Recursive method.
//
// Input:
// - Node * head
// - Node * new_next: the "next" node to be assigned to current node
//
// Return: pointer to new head node
Node * reverse_in_place2(Node * head, Node * new_next)
{
    // Hit the end, just return the last node as new starting node
    if(NULL == head)
    {
        return new_next;
    }
    Node * next = head->next();
    head->set_next(new_next);
    return reverse_in_place2(next, head);
}

// Function: display_till_end
//
// Display a linked list from input node to end.
//
// Input:
// - Node * node
void display_till_end(Node * node)
{
    while(node != NULL)
    {
        std::printf("[%d]->", node->data());
        node = node->next();
    }
    std::printf("NULL\n");
}

// Function: deserialize
//
// Create a linked list from an int array.
//
// Input:
// - int seq[]
// - int size
//
// Return: Head of the created list.
Node * const deserialize(int seq[], int size)
{
    Node * head = new Node(seq[0]);
    Node * end = head;
    for(int i = 1; i < size; ++ i)
    {
        end->set_next(new Node(seq[i]));
        end = end->next();
    }
    return head;
}

// Function: serialize
//
// Store linked list data into an int array.
//
// Input:
// - Node * head: starting node in a linked list to be serialized
// - int seq[]: where values will be stored
// - int size: size of the array
void serialize(Node * node, int seq[], int size)
{
    int i = 0;
    while(node != NULL && i < size)
    {
        seq[i++] = node->data();
        node = node->next();
    }
}

